#include <iostream>

using namespace std;

// 404.左叶子之和
// 给定二叉树的根节点 root ，返回所有左叶子之和。
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(): val(0),left(nullptr),right(nullptr) {}
    TreeNode(int x): val(x),left(nullptr),right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

// 递归解法:使用深度优先遍历
class Solution {
private:
    int res = 0;
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if(root == nullptr)
            return 0;
        dfs(root, false);
        return res;

//        if(root->left == nullptr && root->right == nullptr)
//            return 0;
//
//        int leftSum = 0, rightSum = 0;
//        if(root->left != nullptr) {
//            leftSum = sumOfLeftLeaves(root->left);
//        }
//        if(root->right != nullptr && root->right->left != nullptr) {
//            rightSum = sumOfLeftLeaves(root->right->left);
//        }
//        return leftSum + rightSum;
    }

private:
    // 递归函数，最关键的是引入了bool isLeft来标志是否为左结点
    void dfs(TreeNode* node, bool isLeft) {
        // 最关键的就是这个递归终止条件，对叶子结点的处理
        if(node->left == nullptr && node->right == nullptr) {
            if(isLeft) res += node->val;
            return;
        }

        if(node->left) dfs(node->left, true);
        if(node->right) dfs(node->right, false);
    }
};
int main() {
    std::cout << "Hello, World!" << std::endl;
    return 0;
}
